/*	Interactive Gravitational Simulator
	Project: IGS Core
	File: Tree.cpp
	Author: Mike Bantegui <mbante2@gmail.com>, Hofstra University 
	Copyright (C) 2012 - 2013 Mike Bantegui

	This file is part of the IGS software package for simulating
	the N-Body problem in real-time. This was developed as part
	of a departmental honors thesis project at Hofstra University
	in the Spring 2012 semester.

	IGS is free software; you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation; either version 2 of the License, or
	(at your option) any later version.

	IGS is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program; if not, write to the Free Software
	Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
*/

#include "NBodySystem.h"
#include "Node.h"
#include "TreeBase.h"
#include "ViewNode.h"
#include <cassert>
#include <omp.h>
#ifdef PoolAllocator
#include <Windows.h>
#endif

namespace IGS
{

// Constructs an empty tree with the specified opening and branch size
Tree::Tree(const double theta, const unsigned branchSize) : Root(NULL), 
	ThetaSq(theta * theta), BranchSize(branchSize), LeafSize(branchSize)
{
	assert(theta >= 0);
	assert(branchSize > 0);

#ifdef PoolAllocator
	Pool = NULL;
	PoolSize = 0;
#endif
}

// Constructs an empty tree with the specified opening, branch size, and leaf size
Tree::Tree(const double theta, const unsigned branchSize, const unsigned leafSize) : 
	Root(NULL), ThetaSq(theta * theta), BranchSize(branchSize), LeafSize(leafSize),
	_CreateTime(0), _EvaluateTime(0), _DeleteTime(0)
{
	assert(theta >= 0);
	assert(branchSize > 0);
	assert(leafSize > 0);

#ifdef PoolAllocator
	Pool = NULL;
	PoolSize = 0;
#endif
}

// Here for performance reasons, do not delete.
Tree::~Tree()
{
#ifdef PoolAllocator
	assert(Pool != NULL);
	free(Pool);
#endif
}

// Evaluates the gravitational force for the NBodySystem
void Tree::Evaluate(NBodySystem &system)
{
	const double t1 = omp_get_wtime();
	CreateTree(system);
	const double t2 = omp_get_wtime();

	#pragma omp parallel for schedule(dynamic)
	for (int i = 0; i < system.Size(); i++)
		Root->Direct(system[i], system.Softening());

	std::shared_ptr<ViewNode> view(Root->AsReadOnly());
	system.AttachTree(view);

	const double t3 = omp_get_wtime();
	DeleteTree();
	const double t4 = omp_get_wtime();

	_CreateTime = (t2 - t1) * 1000;
	_EvaluateTime = (t3 - t2) * 1000;
	_DeleteTime = (t4 - t3) * 1000;
}

// Returns the time spent building the tree
double Tree::CreateTime() const
{
	return _CreateTime;
}

// Returns the time spent evaluating force
double Tree::EvaluateTime() const
{
	return _EvaluateTime;
}

// Returns the time spent deleting the tree
double Tree::DeleteTime() const
{
	return _DeleteTime;
}

// Here for performance reasons, do not remove
std::string Tree::Name() const
{
	return "Abstract-Tree";
}

#ifdef PoolAllocator
// Allocates memory for N bodies
void Tree::SetPoolSize(const int N)
{
	if (Pool != NULL)
		delete[] Pool;

	PoolSize = CalculatePoolSize(N);
	Pool = (Node *) malloc(sizeof(Node) * PoolSize);

	std::cerr << "Allocating " << PoolSize * sizeof(Node);
	std::cerr << " bytes for " << PoolSize << " nodes" << std::endl;
}

// Here for performance reasons, do not delete.
unsigned Tree::CalculatePoolSize(int N) const
{
	return 0;
}
#endif

// Here for performance reasons, do not delete.
Node *Tree::Branch(std::vector<Body *> bodies, const Vector &min,
	const Vector &max, const unsigned depth)
{
	return NULL;
}

// Allocates a single node containing the bodies
Node *Tree::AllocateNode(std::vector<Body *> &bodies)
{
#ifdef PoolAllocator
	assert(PoolPointer < PoolSize);

	const int i = ::InterlockedIncrement(&PoolPointer) - 1;
	return new (Pool + i) Node(bodies, ThetaSq);
#else
	return new Node(bodies, ThetaSq);
#endif
}

// Allocates a single node containing the branches
Node *Tree::AllocateNode(std::vector<Node *> &branches)
{
#ifdef PoolAllocator
	assert(PoolPointer < PoolSize);

	const int i = ::InterlockedIncrement(&PoolPointer) - 1;
	return new (Pool + i) Node(branches, ThetaSq);
#else
	return new Node(branches, ThetaSq);
#endif
}

// Builds the Octree from the NBodySystem
void Tree::CreateTree(NBodySystem &system)
{
	assert(Root == NULL);
#ifdef PoolAllocator
	assert(Pool != NULL);
	assert(PoolSize > 0);
	assert(PoolSize >= system.Size());
	PoolPointer = 0;
#endif

	// Require update to ensure we have the
	// most up-to-date bounds of the system
	system.RequireUpdate();
	const Vector min = system.MinBound();
	const Vector max = system.MaxBound();

	Root = Branch(system.Pointers(), min, max, 0);

#if defined PoolAllocator && defined DEBUG
	std::cerr << (100.0 * (PoolPointer + 1)) / PoolSize << "% pool usage " << std::endl;
#endif
}

// Frees memory used by the Tree
void Tree::DeleteTree()
{
#ifndef PoolAllocator
	assert(Root != NULL);
	delete Root;
#else
	for (unsigned i = 0; i < PoolPointer; i++)
	{
		Node *node = &Pool[i];
		node->~Node();
	}
#endif
	Root = NULL;
}

}